package com.zyq.code.slidewindow;

import cn.hutool.core.util.StrUtil;
import cn.hutool.json.JSONUtil;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 滑动窗口算法
 *
 * 概念  滑动窗口算法在一个特定大小的字符串或数组上进行操作，
 * 而不在整个字符串和数组上操作，这样就降低了问题的复杂度，
 * 从而也达到降低了循环的嵌套深度,降低了时间复杂度
 * @author zhangyanqiang
 * @date 2020/12/9
 **/
public class SlideWindow {

    /**
     * 给定一个数组 arr，计算特定长度子数组的个元素之和的最大值
     * 即给定窗口大小 寻找特定的值
     * @param arr
     * @param subArrayLength
     * @return
     */
    public static int maxSum(int[] arr, int subArrayLength){

        System.out.println("原始数组为:"+ JSONUtil.toJsonStr(arr) +", 子数组长度为:"+subArrayLength);
        int len = arr.length;
        if (len < subArrayLength){
            return -1;
        }
        // 计算第一个窗口的值
        int maxSum = 0;
        for (int i =0; i< subArrayLength; i++){
            maxSum += arr[i];
        }

        int sum = maxSum;
        for (int i = subArrayLength; i< len;i++){
            // 新窗口的和 = 前一个窗口的和 + 新进入窗口的值 - 移出窗口的值
            sum += arr[i] - arr[i-subArrayLength];
            maxSum = Math.max(maxSum,sum);
        }
        System.out.println("返回最大和为"+maxSum);
        return maxSum;
    }

    /**
     *
     * 给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。(minimum-window-substring)
     * 即给定对应的值 寻找最小窗口
     * 输入: S = "ADOBECODEBANC", T = "ABC"  输出: "BANC"
     * 注： 方法没跑成功
     * @param source
     * @param template
     * @return
     */
    public static String minWindow(String source,String template){
        System.out.println("source:"+ source);
        System.out.println("template:"+ template);
        // 字典 对象 存储template 各个字符 存在的数量
        Map<String,Integer> dictMap = new HashMap<>(template.length());
        String[] templateArray = StrUtil.split(template,1);
        String[] sourceArray = StrUtil.split(source,1);
        for (String i : templateArray){
            Integer num = dictMap.get(i);
            if (num == null){
                num = 1;
            }else {
                num += 1;
            }
            dictMap.put(i, num);
        }
        // 窗口左端
        int left =0;
        // 窗口右端
        int right = 0;
        // 匹配字符长度
        int templateLen = template.length();
        // 记录包含待定字符串的字符串的长度,方便找出最短的那个
        int sourceLen = source.length();
        // 返回结果
        String result = source;
        int max = Integer.MAX_VALUE;
        // 一开始left = 0, right=0, 左端不变 右端增大
        while (right < source.length()){
            if (dictMap.containsKey(sourceArray[right])){
                // 字典里该字符对应的值大于0时说明该字符在窗口内还未全部出现
                Integer num = dictMap.get(sourceArray[right]);
                if (num != null && num>0){
                    templateLen --;
                    num --;
                    dictMap.put(sourceArray[right],num);
                }
            }
            right ++;
            // 找到包含待定字符串的字符后,开始移动左端
            while (templateLen == 0){
                //若新窗口的长度小于之前最小长度的窗口,则替换掉
                if (max>right - left){
                    max = right - left;
                    result = source.substring(left, right);
                }
                // 当左端字符在待定字符串t里时,有可能新窗口不完全包含t了
                String key = sourceArray[left];
                if (dictMap.containsKey(key)){
                    Integer num = dictMap.get(key);
                    num ++;
                    dictMap.put(key, num);
                    //当字典内某字符的值大于1时,表示窗口又缺该字符了
                    if (num > 0){
                        templateLen ++;
                    }
                }
                left ++;
            }
        }

        System.out.println("result:"+result);
        return result;
    }

    public static void main(String[] args) {

        Random random = new Random();
        int[] array = new int[10];
        for (int i=0; i< 10; i++){
            array[i] = random.nextInt(10);
        }
        int maxSum = maxSum(array,3);
       minWindow("ADOBECODEBANC","ABC");
    }

}
